#include <iostream>
#include <queue>
#include <vector>

using namespace std;
class Solution
{
 public:
  vector<int> printMatrix(vector<vector<int>>& matrix)
  {
    vector<int> res;
    if (matrix.empty()) return res;
    int n = matrix.size(), m = matrix[0].size();
    vector<vector<bool>> st(n, vector<bool>(m, false));
    int dx[4] = {-1, 0, 1, 0}, dy = [4] = {0, 1, 0, -1};
    int x = 0, y = 0, d = 1;

    // 暴力搜索
    for (int k = 0; k < n * m; k++)
    {
      res.push_back(matrix[x][y]);
      st[x][y] = true;  // 标志位已访问

      int a = x + dx[d], b = y + dy[d];
      if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
      {
        d = (d + 1) % 4;  // 换方向：四个方向为 上右下左
        // 换方向后重新确定下一个打印的未访问的元素
        a = x + dx[d], b = y + dy[d];
      }
      x = a, y = b;
    }
    return res;
  }
};
